package Tree;
import java.util.*;
class Node{
    int value;//树中存储的数据
    Node firstChild;//第一个孩子的引用
    Node nextBrother;//下一个兄弟引用
}



    /**
     * @Author 12629
     * @Description：
     */
    public class MyTree {
        static class TreeNode {
            public char val;
            public TreeNode left;//左孩子的引用
            public TreeNode right;//右孩子的引用

            public TreeNode(char val) {
                this.val = val;
            }
        }

        public TreeNode createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');

            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;//就是根节点
        }
        // 前序遍历
        public void preOrder(TreeNode root) {
            if(root == null) {
                return;
            }
            System.out.print(root.val+" ");
            //递归遍历左子树
            preOrder(root.left);
            //递归遍历右子树
            preOrder(root.right);
        }

        // 中序遍历
        public void inOrder(TreeNode root) {
            if(root == null) {
                return;
            }
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }


        // 后序遍历
        public void postOrder(TreeNode root) {
            if(root == null) {
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }

        // 获取树中节点的个数
        public int size(TreeNode root) {
            if(root == null) {
                return 0;
            }
            int ret = size(root.left) +
                    size(root.right)+1;
            return ret;
        }

        public static int nodeSize;
        public void size2(TreeNode root) {
            if(root == null) {
                return ;
            }
            nodeSize++;
            size2(root.left);
            size2(root.right);
        }

        /**
         * 求叶子节点的个数
         * @param root
         * @return
         */
        public int getLeafNodeCount(TreeNode root) {
            if(root == null) {
                return 0;
            }

            if(root.left == null && root.right == null) {
                return 1;
            }

            return getLeafNodeCount(root.left)
                    + getLeafNodeCount(root.right);
        }

        public int leafSize;
        public void getLeafNodeCount2(TreeNode root) {
            if(root == null) {
                return ;
            }

            if(root.left == null && root.right == null) {
                leafSize++;
            }
            getLeafNodeCount2(root.left);
            getLeafNodeCount2(root.right);
        }
        /*
        第K层有多少个节点？
         */
        public int getKLevelNodeCount(TreeNode root,int k) {
            if(root == null) {
                return 0;
            }
            if(k == 1) {
                return 1;
            }
            return getKLevelNodeCount(root.left,k-1) +
                    getKLevelNodeCount(root.right,k-1);
        }

        /*
        时间复杂度：O(N)
         */
        public int getHeight(TreeNode root) {
            if(root == null) {
                return 0;
            }
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);

            return leftHeight > rightHeight ?
                    leftHeight+1:rightHeight+1;
       /* return getHeight(root.left) > getHeight(root.right) ?
                getHeight(root.left)+1:getHeight(root.right)+1;*/
        }

        /**
         * 遍历二叉树 找到val所在的节点
         * @param root
         * @param val
         * @return
         */
        public TreeNode find(TreeNode root, char val) {
            if(root == null) {
                return null;
            }
            if(root.val == val) {
                return root;
            }

            TreeNode ret = find(root.left,val);
            if(ret != null) {
                return ret;
            }

            ret = find(root.right,val);
            if(ret != null) {
                return ret;
            }
            return null;
        }


        /**
         * 时间复杂度：O(min(m,n))
         * @param p m个节点
         * @param q n个节点
         * @return
         */
        public boolean isSameTree(TreeNode p, TreeNode q) {
            //1. 一个为空 一个不为空 [结构上不一样]
            if(p != null && q == null || p == null && q != null) {
                return false;
            }

            //2. 第一步走完之后，要么都为空，要么都不为空 两个都是空
            if(p == null && q == null) {
                return true;
            }

            //3. 都不为空
            if(p.val != q.val) {
                return false;
            }

            //4. 此时代表 2个都不为空 通知val值也是一样的！
            //5. 说明根节点相同，接下来判断两棵树的左 和 两棵树的右 是不是同时相同
            return isSameTree(p.left,q.left)
                    && isSameTree(p.right,q.right);
        }


        /**
         * 时间复杂度：O(m*n)
         * @param root m
         * @param subRoot n
         * @return
         */
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if(root == null) {
                return false;
            }
            if(isSameTree(root,subRoot)) {
                return true;
            }
            if(isSubtree(root.left,subRoot)) {
                return true;
            }
            if(isSubtree(root.right,subRoot)) {
                return true;
            }
            return false;
        }

        public TreeNode invertTree(TreeNode root) {
            if(root == null) {
                return null;
            }
            //减少一些递归 和 交换的次数
            if(root.left == null && root.right == null) {
                return root;
            }

            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;

            invertTree(root.left);
            invertTree(root.right);

            return root;
        }

        //时间复杂度：O(N^2)
        public boolean isBalanced(TreeNode root) {
            if(root == null) return true;

            int leftH = maxDepth(root.left);
            int rightH = maxDepth(root.right);

            return Math.abs(leftH - rightH) <= 1
                    && isBalanced(root.left)
                    && isBalanced(root.right);
        }
        public int maxDepth(TreeNode root) {
            if(root == null) {
                return 0;
            }
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);

            return leftHeight > rightHeight ?
                    leftHeight+1:rightHeight+1;
        }

        public boolean isBalanced2(TreeNode root) {
            if(root == null) return true;
            return maxDepth(root) >= 1;
        }
        public int maxDepth2(TreeNode root) {
            if(root == null) {
                return 0;
            }
            int leftHeight = maxDepth2(root.left);
            if(leftHeight < 0) {
                return -1;
            }
            int rightHeight = maxDepth2(root.right);
            if(rightHeight < 0) {
                return -1;
            }
            if(Math.abs(leftHeight - rightHeight) <= 1) {
                return Math.max(leftHeight,rightHeight) + 1;
            }else {
                return -1;
            }
        }

        public int maxDepth3(TreeNode root) {
            if(root == null) {
                return 0;
            }
            int leftHeight = maxDepth3(root.left);

            int rightHeight = maxDepth3(root.right);

            if(leftHeight >= 0 && rightHeight >= 0 &&
                    Math.abs(leftHeight - rightHeight) <= 1) {
                return Math.max(leftHeight,rightHeight) + 1;
            }else {
                return -1;
            }
        }

        public boolean isSymmetric(TreeNode root) {
            if(root == null) return true;
            return isSymmetricChild(root.left,root.right);
        }
        public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
            //1. 检查结构是否相同 -> 一个为空 一个不为空
            if(leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
                return false;
            }
            //2. 检查结构是否相同 -> 处理 【两个都为空】 和 两个都不为空
            if(leftTree == null && rightTree == null) {
                return true;
            }
            //3. 检查结构是否相同 -> 处理 两个都为空 和 【两个都不为空，判断值一样吗】
            if(leftTree.val != rightTree.val) {
                return false;
            }
            //4. 此时两个引用 都不为空 同时 节点的值一样
            //5. 开始判断是否对称
            //6. 满足 左子树的左  和  右子树的 右对称  同时 左子树的右  和 右子树的左 对称
            return isSymmetricChild(leftTree.left,rightTree.right)
                    && isSymmetricChild(leftTree.right,rightTree.left) ;
        }

    /*
    class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static int i = 0;
    public static TreeNode cretateTree(String str) {
        TreeNode root = null;
        if(str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = cretateTree(str);
            root.right = cretateTree(str);
        }else {
            i++;
        }
        return root;
    }

    public static void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = cretateTree(str);
            inorder(root);
        }
    }
}
     */

        public void levelOrder(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            if(root == null) {
                return;
            }
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                System.out.print(cur.val+" ");
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            System.out.println();
        }

        /**
         * 层序遍历
         * @param root
         * @return
         */
    /*public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();//1
            List<Integer> list = new ArrayList<>();//每层
            while (size > 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;//0
            }
            ret.add(list);
        }
        return ret;
    }*/

        public boolean isCompleteTree(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            if(root == null) return true;
            queue.offer(root);

            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                if(cur == null) {
                    break;
                }
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            while (!queue.isEmpty()) {
                TreeNode node = queue.peek();
                if(node != null) {
                    return false;
                }else {
                    queue.poll();
                }
            }
            return true;
        }



        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) {
                return null;
            }
            if(root == p || root == q) {
                return root;
            }
            TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
            TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
            //两边都不为空
            if(leftTree != null && rightTree != null) {
                return root;
            }else if(leftTree != null) {
                //左边不为空
                return leftTree;
            } else {
                //右边不为空
                return rightTree;
            }
        }

        public TreeNode lowestCommonAncestor2(TreeNode root,
                                              TreeNode p, TreeNode q) {
            if(root == null) {
                return root;
            }
            //1. 获取 root 到 指定 节点  路径上的所有节点
            Stack<TreeNode> stackP = new Stack<>();
            getPath(root,p,stackP);

            Stack<TreeNode> stackQ = new Stack<>();
            getPath(root,q,stackQ);

            //2. 上述代码执行完成 对应栈当中 存储了 指定路径上的所有节点

            int sizeP = stackP.size();
            int sizeQ = stackQ.size();

            if(sizeP > sizeQ) {
                int size = sizeP - sizeQ;
                while (size != 0) {
                    stackP.pop();
                    size--;
                }
            }else {
                int size = sizeQ - sizeP;
                while (size != 0) {
                    stackQ.pop();
                    size--;
                }
            }
            //3. 上述if语句执行完成 两个栈当中的元素个数是一样的
            while (!stackP.isEmpty() && !stackQ.isEmpty()) {
                if(stackP.peek() == stackQ.peek()) {
                    return stackP.peek();
                }else {
                    stackP.pop();
                    stackQ.pop();
                }
            }
            return null;
        }

        /**
         * 把root节点 到  指定节点node 路径上的所有节点 都存储在栈当中
         * @param root
         * @param node
         * @param stack
         * @return
         */
        public boolean getPath(TreeNode root, TreeNode node,
                               Stack<TreeNode> stack) {
            if(root == null) {
                return false;
            }
            stack.push(root);
            if(root == node) {
                return true;
            }
            boolean flg = getPath(root.left,node,stack);
            if(flg) {
                return true;
            }
            boolean flg2 = getPath(root.right,node,stack);
            if(flg2) {
                return true;
            }
            stack.pop();
            return false;
        }


        public void preOrderNot(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;

            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    System.out.print(cur.val +" ");
                    cur = cur.left;
                }

                TreeNode top = stack.pop();
                cur = top.right;
            }
        }

        public void inOrderNot(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;

            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }

                TreeNode top = stack.pop();
                System.out.print(top.val + " ");
                cur = top.right;
            }
        }

        public void postOrderNot(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode prev = null;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode top = stack.peek();
                if (top.right == null || top.right == prev) {
                    //打印当前top 并且弹出
                    stack.pop();
                    System.out.print(top.val + " ");
                    prev = top;
                } else {
                    cur = top.right;
                }
            }
        }

    /*
    前序 中序 创建二叉树
    class Solution {

    public int preIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChilde(preorder,inorder,0,inorder.length-1);
    }

    private TreeNode buildTreeChilde(int[] preorder, int[] inorder,int inBegin,int inEnd) {
        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);

        int rootIndex = findRootIndex(inorder,inBegin,inEnd,preorder[preIndex]);

        preIndex++;

        root.left = buildTreeChilde(preorder,inorder,inBegin,rootIndex-1);
        root.right = buildTreeChilde(preorder,inorder,rootIndex+1,inEnd);

        return root;
    }

    private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
        for(int i = inBegin; i <= inEnd;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
     */


    /*
    中序 和 后序  创建二叉树
    class Solution {
    public int postIndex = 0;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] inorder,int[] postorder,int inBegin,int inEnd) {
        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findRootIndex(inorder,inBegin,inEnd,postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(inorder,postorder,rootIndex+1,inEnd);
        root.left = buildTreeChild(inorder,postorder,inBegin,rootIndex-1);
        return root;
    }

    private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
        for(int i = inBegin; i <= inEnd;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
     */

        public String tree2str(TreeNode root) {
            StringBuilder stringBuilder = new StringBuilder();
            tree2strChild(root,stringBuilder);
            return stringBuilder.toString();
        }
        private void tree2strChild(TreeNode root,StringBuilder stringBuilder) {
            if(root == null) return ;
            stringBuilder.append(root.val);//1
            if(root.left != null) {
                stringBuilder.append("(");
                tree2strChild(root.left,stringBuilder);
                stringBuilder.append(")");
            }else {
                //左边为空  右边也为空
                if(root.right == null) {
                    return;
                }else {
                    stringBuilder.append("()");
                }
            }
            //处理root右树的情况
            if(root.right == null) {
                return;
            }else {
                stringBuilder.append("(");
                tree2strChild(root.right,stringBuilder);
                stringBuilder.append(")");
            }
        }
    }

